Internet protocol (IP) networks are increasingly being used for delivery of high bit rate video. However, IP networks are subject to network delays, dropped packets, and congestion, all of which pose serious problems for streaming video applications. For example, if a video frame in a data packet contains an error, the entire packet is dropped by the IP network and must be retransmitted. However, in the context of streaming video applications, video frames are required to be presented for viewing in a particular order and at a particular rate to present the illusion of continuous video playback. Often a portion of a video frame included in a dropped data packet cannot be retransmitted before the frame is to be displayed in playback of the streaming video. As a result, the frame will not be available for display when needed.
Some transport protocols for streaming video implement forward error correction (FEC) to recover dropped packets without requiring retransmission. FEC adds metadata redundancy to a data packet by encoding the data packet prior to transmission. The added redundancy is used to detect and recover missing or corrupt portions of the received data. In some protocols, an exclusive-OR (XOR) based FEC algorithm can be implemented in hardware for high-throughput streaming video applications. The XOR-based FEC algorithm can logically arrange data blocks of a data stream into rows and columns of a two dimensional matrix. Depending on the implementation, the data blocks may be data packets, video frames, or other partition of a data stream. For ease of reference, data blocks of the matrix may be referred to as media datagrams herein.
FEC data is computed for each column of the two-dimensional matrix. For ease of reference, the FEC data computed for a column is referred to as a column FEC datagram. To calculate a column FEC datagram, a bitwise XOR of the payload of media datagrams in the column is computed. For example, an XOR is computed for the first two media datagrams in the column. For each following media datagram in the column, a bitwise XOR of the datagram payload and the previous XOR result is computed. The result of the XOR operations is a column FEC datagram that may be used to recover a missing media datagram of the column. If one of the media datagrams is missing, a bitwise XOR of other media datagrams in the column and the column FEC datagram results in the missing media datagram.
The XOR-based FEC algorithm used in the above implementations can recover a missing datagram only if there is no more than one missing datagram in the column. FEC datagrams may also be calculated for each row and column in the two-dimensional matrix. Similar to the description of column FEC datagrams, FEC data is computed for each row of the two-dimensional matrix. For ease of reference, the FEC data computed for a row is referred to as a row FEC datagram. To calculate an FEC datagram for a row, a bitwise XOR of the payload of media datagrams in the row is computed in a similar manner to that described for a column FEC datagram. If one of the media datagrams in the row is missing, a bitwise XOR of other media datagrams in the row and the row FEC datagram results in the missing media datagram.
Even if a row is missing multiple media datagrams, the datagrams may be recoverable in their columns using the column FEC datagrams. For example, recovery of one of the missing media datagrams in the row through column recovery using a column FEC datagram may result in the row having only one missing media datagram, which can then be recovered using the row FEC datagram.
By iteratively searching for recoverable media datagrams (i.e., missing media datagrams that can be recovered via a row or column FEC datagram), a larger number of missing datagrams may be recovered. However, existing methods for locating recoverable media datagrams in a two-dimensional matrix are inefficient and often may not be implemented in hardware. As a result, the methods may not be capable of recovering missing video frames in time for proper display during playback.
One or more embodiments may address one or more of the above issues.